lib/Mi manual de algoritmos/version_world_finals_2009/src/grafos/dinic.cpp

   1 /*
   2   ACRush's Dinic algorithm for maximum flow
   3   Complexity: O(E V^2)
   4
   5   Usage:
   6   init(number of nodes, source, sink);
   7   Create graph using add_edge(int u, int v, int c1, int c2):
   8   This adds two directed edges: u -> v with capacity c1
   9     and v -> u with capacity c2.
  10   c2 by default is 0.
  11   After creating the graph, nedge contains the number of
  12      total edges.
  13   dinic_flow();
  14   This doesn't modify the capacity of the original graph,
  15      so you can run the algorithm several times on the same
  16      graph.
  17   If you want to run the algorithm with different sources/sinks
  18      assign the correct value to src and dest before calling
  19      dinic_flow().
  20  */
  21
  22 const int maxnode=2*55 + 5; const int
  23 maxedge=maxnode*(maxnode-1)/2; const int oo=1000000000;
  24
  25 int node,src,dest,nedge; int
  26 head[maxnode],point[maxedge],next[maxedge],
  27 flow[maxedge],capa[maxedge];
  28 int dist[maxnode],Q[maxnode],work[maxnode];
  29
  30 void init(int _node,int _src,int _dest) { node=_node;
  31 src=_src; dest=_dest; for (int i=0;i<node;i++) head[i]=-1;
  32 nedge=0; } void add_edge(int u,int v,int c1,int c2 = 0) {
  33 point[nedge]=v,capa[nedge]=c1,flow[nedge]=0,
  34 next[nedge]=head[u],head[u]=(nedge++);
  35 point[nedge]=u,capa[nedge]=c2,flow[nedge]=0,
  36 next[nedge]=head[v],head[v]=(nedge++);
  37 } bool dinic_bfs() { memset(dist,255,sizeof(dist));
  38 dist[src]=0; int sizeQ=0; Q[sizeQ++]=src; for (int
  39 cl=0;cl<sizeQ;cl++) for (int k=Q[cl],i=head[k];i>=0;i=next[i])
  40 if (flow[i]<capa[i] && dist[point[i]]<0) {
  41 dist[point[i]]=dist[k]+1; Q[sizeQ++]=point[i]; } return
  42 dist[dest]>=0; } int dinic_dfs(int x,int exp) { if (x==dest)
  43 return exp; for (int &i=work[x];i>=0;i=next[i]) { int
  44 v=point[i],tmp; if (flow[i]<capa[i] && dist[v]==dist[x]+1 &&
  45 (tmp=dinic_dfs(v,min(exp,capa[i]-flow[i])))>0) { flow[i]+=tmp;
  46 flow[i^1]-=tmp; return tmp; } } return 0; } int dinic_flow() {
  47 for (int i=0; i<nedge; ++i) flow[i] = 0; int result=0; while
  48 (dinic_bfs()) { for (int i=0;i<node;i++) work[i]=head[i];
  49 while (1) { int delta=dinic_dfs(src,oo); if (delta==0) break;
  50 result+=delta; } } return result; }